|
In mathematics, the telephone numbers or involution numbers are a sequence of integers that count the number of connection patterns in a telephone system with subscribers, where connections are made between pairs of subscribers. These numbers also describe the number of matchings (the Hosoya index) of a complete graph on vertices, the number of permutations on elements that are involutions, the sum of absolute values of coefficients of the Hermite polynomials, the number of standard Young tableaux with cells, and the sum of the degrees of the irreducible representations of the symmetric group. Involution numbers were first studied in 1800 by Heinrich August Rothe, who gave a recurrence equation by which they may be calculated,〔.〕 giving the values (starting from ) :1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... . ==Applications== John Riordan provides the following explanation for these numbers: suppose that a telephone service has subscribers, any two of whom may be connected to each other by a telephone call. How many different patterns of connection are possible? For instance, with three subscribers, there are three ways of forming a single telephone call, and one additional pattern in which no calls are being made, for a total of four patterns.〔.〕 For this reason, the numbers counting how many patterns are possible are sometimes called the telephone numbers.〔.〕〔.〕 Every pattern of pairwise connections between subscribers defines an involution, a permutation of the subscribers that is its own inverse, in which two subscribers who are making a call to each other are swapped with each other and all remaining subscribers stay in place. Conversely, every possible involution has the form of a set of pairwise swaps of this type. Therefore, the telephone numbers also count involutions. The problem of counting involutions was the original combinatorial enumeration problem studied by Rothe in 1800〔 and these numbers have also been called involution numbers.〔.〕〔.〕 In graph theory, a subset of the edges of a graph that touches each vertex at most once is called a matching. The number of different matchings of a given graph is important in chemical graph theory, where the graphs model molecules and the number of matchings is known as the Hosoya index. The largest possible Hosoya index of an -vertex graph is given by the complete graphs, for which any pattern of pairwise connections is possible; thus, the Hosoya index of a complete graph on vertices is the same as the th telephone number.〔.〕 A Ferrers diagram is a geometric shape formed by a collection of squares in the plane, grouped into a polyomino with a horizontal top edge, a vertical left edge, and a single monotonic chain of horizontal and vertical bottom and right edges. A standard Young tableau is formed by placing the numbers from 1 to into these squares in such a way that the numbers increase from left to right and from top to bottom throughout the tableau. According to the Robinson–Schensted correspondence, permutations correspond one-for-one with ordered pairs of standard Young tableaux. Inverting a permutation corresponds to swapping the two tableaux, and so the self-inverse permutations correspond to single tableaux, paired with themselves.〔A direct bijection between involutions and tableaux, inspired by the recurrence relation for the telephone numbers, is given by .〕 Thus, the telephone numbers also count the number of Young tableaux with squares.〔 In representation theory, the Ferrers diagrams correspond to the irreducible representations of the symmetric group of permutations, and the Young tableaux with a given shape form a basis of the irreducible representation with that shape. Therefore, the telephone numbers give the sum of the degrees of the irreducible representations. In the mathematics of chess, the telephone numbers count the number of ways to place rooks on an chessboard in such a way that no two rooks attack each other (the so-called eight rooks puzzle), and in such a way that the configuration of the rooks is symmetric under a diagonal reflection of the board. Via the Pólya enumeration theorem, these numbers form one of the key components of a formula for the overall number of "essentially different" configurations of mutually non-attacking rooks, where two configurations are counted as essentially different if there is no symmetry of the board that takes one into the other.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Telephone number (mathematics)」の詳細全文を読む スポンサード リンク
|